package LeetcodeTest_twenty_five;
//求和路径

import java.util.Scanner;

import static java.lang.System.out;

public class pathSum
{
    public static void main(String[] args)
    {
        TreeNode root=new TreeNode();
        root=solution.createTree(root);
        System.out.println(solution.pathSum(root,9));
    }
}
class solution
{
    public static int count=0;
    public static int pathSum(TreeNode root, int sum)
    {
        difs1(root,sum);
        return count;
    }
    public static void difs1(TreeNode root,int sum)
    {
        if(root!=null)
        {
            difs2(root,sum,0);
            difs1(root.left,sum);
            difs1(root.right,sum);
        }
    }
    public static void difs2(TreeNode root,int sum,int summary)
    {
        if(root!=null)
        {
            summary=summary+root.val;
            if(summary==sum)
                count++;
            difs2(root.left,sum,summary);
            difs2(root.right,sum,summary);
            summary=summary-root.val;
        }
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
}